\label{alg:parser}       
For PPCR to work we need some slight modifications in the LR parsing algorithm.
The following Perl pseudocode describes the PPCR parsing algorithm. 
Our notation follows the conventions 
used in \cite{aho2006}:

\begin{VERBATIM}[codes={\catcode`$=3\catcode`\_=8\catcode`^=7}]
method PPCRparse(LRParser \Dr{}p)          \textit{# The LR parser object}
 my @stack;                            \textit{# The LR parsing stack}
 my \Dr{}s0 = \Dr{}p->startstate;
 push(@stack, \Dr{}s0);       \textit{# Push the start state in the stack}
 my \Dr{}b = \Dr{}p->yylex();                        \textit{# Get next token}
 forever do \B{}
   my \Dr{}s = top();     \textit{# Get the state in the top of the stack}
   my \Dr{}a = \Dr{}b;
   my \Dr{}act; 
   \textbf{if (\Dr{}p->isConflictive(\Dr{}s, \Dr{}a)) \Dr{}p->conflictHandler(\Dr{}s, \Dr{}a); } \label{vrb:conflictbegin}
   \Dr{}act = \Dr{}p->action(\Dr{}s->state, \Dr{}a);  \label{vrb:action}
   switch (\Dr{}act) \B{}
     case "shift t" : 
       my \Dr{}t;
       \Dr{}t->\B{}state\BB{} = t;
       \Dr{}t->\B{}attr\BB{}  = \Dr{}a->\B{}attr\BB{};
       push(\Dr{}t);               \textit{# Store the state in the stack}
       \Dr{}b = \Dr{}p->yylex();                     \textit{# Get next token}
       break;
     case "reduce A $\rightarrow \alpha$" : 
       my \Dr{}r;
                   \textit{# Get the attributes of the |$\alpha$| top states}
       my @ats = getAttributes(@stack[-|$\alpha$| .. -1]); 
       \Dr{}r->\B{}attr\BB{} = \Dr{}p->Sem\B{}A->$\alpha$\BB{}->(@ats); \label{vrb:semcall}
       pop(|$\alpha$|);                       \textit{# Pop length($\alpha$) states}
       my \Dr{}t = top();
       \Dr{}r->\B{}state\BB{} = \Dr{}p->goto(\Dr{}t, A); \label{vrb:goto}
       push(\Dr{}r); 
       break;
     case "accept" : return (\Dr{}s->attr); 
     default : \Dr{}p->yyerror("syntax error");
   \BB{}
\end{VERBATIM}

As usual \verb#|#$\alpha$\verb#|# denotes the length of string $\alpha$.
The call \verb|top()| returns the state in the top of the stack,
while the call \verb|pop(k)| extracts the top \verb|k| states from the stack.
The notations \verb|$a->{attr}| and \verb|$t->{attr}| make reference to the
attribute associated with the token  \verb|$a| and to the attribute associated with the state 
\verb|$s|.
The call \verb#getAttributes(@stack[-|#$\alpha$\verb#| .. -1])# returns the list of attributes
of the \verb#|#$\alpha$\verb#|#  top states in the stack. A negative index in Perl starts
from the end of the array, thus \verb|$stack[-1]| is the state in the top of the stack.
The hash entry \verb|$Sem{A|$\rightarrow \alpha$\verb|}| is a reference to the semantic code 
associated with production \verb|A|$\rightarrow \alpha$. 
Such code is called in line \ref{vrb:semcall},
whenever a reduction by \verb|A|$\rightarrow \alpha$ is detected. 


The calls to \verb|action| (line \ref{vrb:action}) and \verb|goto| (line \ref{vrb:goto}) 
respectively return the corresponding entries
of the \verb|ACTION| and \verb|GOTO| parsing tables.

The only change is in line \ref{vrb:conflictbegin}.
If the couple state-token is conflictive, i.e. if the LR action table was multivalued, the 
conflict handler for such entry is called to decide the correct action. 

This give us a measure 
of the overhead introduced by PPCR per iteration: the cost of checking the condition (line \ref{vrb:conflictbegin}). In case 
of being a conflictive state we also have to add the cost of executing the handler, 
which usually takes constant time: it checks the attribute containing the
result of the last explorer execution and changes accordingly the corresponding entry of the action table. 
Furthermore, a yacc compiler can generate optimal code by using
the classical LR algorithm when no conflict handlers were defined.

The correspondence between conflictive pairs $(state, token)$ 
and conflict handlers
is generated by the compiler during the construction of the LR tables using the information gathered from
the \verb|%PREC| directives.

An additional modification is needed when generating the LR tables for the sub-grammar starting in $A$.
Nested parsers for a nonterminal $A$ must accept prefixes  of the incoming input not necessarily
terminated by the end of input token. The action table is modified to have an $accept$ action 
for each entry $(s, a)$
where the state $s$ has an LR item $[A' \rightarrow A_\uparrow , a]$ where $a \in FOLLOW(A)$.
That is, it accepts when something derivable from $A$ has been seen and the next token is a legal one.
Here $A'$ denotes the super-start symbol for the sub-grammar starting in $A$. The set $FOLLOW(A)$ 
is the set of tokens $b$ in the super-grammar such that exists a derivation 
$S  \stackrel{*}{\Longrightarrow}  \alpha A b \beta$.
The end of input is also included in $FOLLOW(A)$ if, and only if,
exists a derivation $S \stackrel{*}{\Longrightarrow} \alpha A$.

For each explorer definition the current implementation of the \verb|eyapp| compiler 
creates an auxiliary syntactic variable  
whose only empty production has as associated semantic action
the code defined by the \verb|%explorer| directive. Such code can be explicit 
(see \cite{lgforte} for examples)
or implicit as in the example in section
\ref{section:inherentlyambiguous} 
. The points where the 
\verb|%conflict?| directive appears inside the body
are substituted by that variable. 
The execution of the exploration code is an additional source of overhead.
The programmer must choose the exploration point in a way that 
\begin{itemize}
\item
makes easy the nested parsing and the recollection of the information needed to take the decision
\item
minimizes the number of times it is executed and
the time taken by the decision/exploration code,
\item
guarantees that the decision taken will be valid when the next visit to the conflict state
occurs 
and
\item
does not introduce new conflicts. 
This restriction can be lifted if, instead of implementing explorers 
through a syntactic variable, the PPCR algorithm is modified to
execute the exploring code when the state is an explorer-state.
\end{itemize}

The last version of \verb|eyapp| can be obtained from  \cite{Rodriguez:Leon}.
There is also a repository of difficult and conflictive yacc grammars with their corresponding
PPCR solutions in \cite{lgforte}. Contributions are welcome.

